package com.feiuxiu.datastructure.array;

/**
 * description: 循环数组
 * author: feixiu
 * date:2025/9/9 21:46
 */
public class CycleArray<T> {

    // 数据数组
    private T[] arr;

    private int start;
    private int end;
    // count 代表当前数组中的元素个数
    private int count;
    //数组的容量
    private int size;

    public CycleArray() {
        this(1);
    }

    public CycleArray(int size) {
        this.size = size;
        this.arr=(T[]) new Object[size];
        this.count=0;
        //start 指向第一个有效元素的索引，闭区间
        this.start=0;
        //end 是一个开区间，即end 指向最后一个有效元素的下一个位置索引
        this.end=0;
    }
    //自动扩缩容辅助函数
    private void resize(int newSize){
        // 创建新的数组
        T[] newArr= (T[]) new Object[size];

        for (int i = 0; i < count; i++) {
            newArr[i]=arr[(start+i)%size];
        }
        arr=newArr;
        //重置start 和end 指针
        start=0;
        end=count;
        size=newSize;
    }

    public boolean isFull(){
        return count==size;
    }
    public int size(){
        return count;
    }
    public boolean isEmpty(){
        return count==0;
    }

    // 在数组头部添加元素，时间复杂度 O(1)
    public void addFirst(T val){
        // 当数组满的时候，扩容为原来的两倍
        if (isFull()){
            resize(size*2);
        }
        start=(start-1 +size)%size;//之所以加上size ，就是为了防止 -1 之后变成负数，不方便计算
        arr[start]=val;
        count++;
    }

    public void removeFirst(){
        if (isEmpty()){
            throw new IllegalStateException("Array is empty");
        }
        // 因为start是闭区间，所以先赋值，再右移
        arr[start]=null;
        start = (start+1)%size;
        count--;
        // 如果数组元素数量减少到原来大小的四分之一，则减少数组大小为一半
        if (count>0 && count == size/4){
            resize(size/2);
        }
    }

    public void addLast(T val){
        // 当数组满的时候，扩容为原来的两倍
        if (isFull()){
            resize(size*2);
        }
        arr[end]=val;
        end=(end+1)%size;
        count++;
    }

    public void removeLast(){
        if (isEmpty()){
            throw new IllegalStateException("Array is empty");
        }

        end=(end-1+size)%size;
        arr[end]=null;
        count--;
        // 如果数组元素数量减少到原来大小的四分之一，则减少数组大小为一半
        if (count>0 && count == size/4){
            resize(size/2);
        }
    }

    public T getFirst(){
        // 当数组满的时候，扩容为原来的两倍
        if (isEmpty()){
            throw new IllegalStateException("Array is empty");
        }

        return arr[start];
    }

    public T getLast(){
        // 当数组满的时候，扩容为原来的两倍
        if (isEmpty()){
            throw new IllegalStateException("Array is empty");
        }

        return arr[(end-1+size)%size];
    }

}
